// 二叉排序树
//>>>>>>>>>>>>>>>>>>>>>>>>引入头文件<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
#include <stdio.h>       //使用了标准库函数 
#include <stdlib.h>      //使用了动态内存分配函数
#include <windows.h>
//>>>>>>>>>>>>>>>>>>>>>>自定义符号常量<<<<<<<<<<<<<<<<<<<<<<<<<<< 
 
#define OVERFLOW -2          //内存溢出错误常量
#define OK 1                 //表示操作正确的常量 
#define ERROR 0              //表示操作错误的常量
#define TRUE 1               //表示逻辑正确的常量 
#define FALSE 0              //表示逻辑错误的常量

//>>>>>>>>>>>>>>>>>>>>>自定义数据类型<<<<<<<<<<<<<<<<<<<<<<<<<<<

typedef int  Status;      //状态标志 

//----------------二叉树的二叉链表存储表示-------------------- 
typedef struct BiNode{
	//数据域 
	int  data;
	//左右孩子结点指针
	struct BiNode  *lchild, *rchild; 
}BiNode, *BiTree;

//-----------------------二叉排序树的主要操作---------------------------

//>>>>>>>>>>>>>>>>>>>>>  1.二叉排序树的构建  <<<<<<<<<<<<<<<<<<<<<<<<<<<

/*
	函数：CreateBST
	参数：BiTree *T 二级指针，二叉排序树引用 
	返回值：状态码，操作成功返回OK 
	作用：根据用户输入创建一棵二叉排序树 
*/
Status createBST(BiTree *T){
    //二叉排序树插入结点函数声明
	Status insertBST(BiTree *T, int data);

    //二叉排序树顶点总数 
    int num;

    //保存输入的关键字
    int data;

 	//确定树中的顶点总数 
    printf("您想创建一棵含有几个顶点的二叉排序树，请输入顶点数，并按回车确认：");   
    scanf("%d", &num);

     //输入关键字 
    printf("请输入%d个整数作为关键字，中间用空格隔开，并按Enter确认\n", num);
    for(int i = 0; i < num; i++) {
    	scanf("%d", &data);
     	insertBST(T, data);
    }
    
    //操作成功 
    printf("二叉排序树创建完成\n"); 
    return OK;   
}

//>>>>>>>>>>>>>>>>>>>  2.二叉排序树的遍历  <<<<<<<<<<<<<<<<<<<<

/*
	函数：PrintElement
	参数：BiTree &T 二叉排序树引用 
	返回值：状态码，操作成功返回OK 
	作用：元素访问函数，输出关键字key
*/
Status printElement(int key) {
	
	//以控制台打印key的方式访问关键字 
	printf(" %d ", key);
	
	//操作成功 
	return OK;
}

/*
	函数：InOrderTraverse
	参数：BiTree T 二叉排序树T
		  Status(* Visit)(KeyType) 元素访问函数 
	返回值：状态码，操作成功返回OK，操作失败返回ERROR 
	作用：采用二叉链表存储结构，Visit是对数据元素操作的应用函数
	      中序遍历二叉树T的递归算法，对每个数据元素调用函数Visit
*/
Status inOrderTraverse(BiTree *T, Status(* visit)(int)){
	// 根节点不为空
	if(*T){
		// 遍历左节点
		if(inOrderTraverse( &(*T)->lchild,visit)){
			// 遍历根节点
			if(visit((*T)->data)){
				// 遍历右节点
				if(inOrderTraverse( &(*T)->rchild,visit)){
					return OK;
				}
			}
		}

		return ERROR;
	}else{
		// 表示输入的是一个叶子节点的子节点：null
		return OK;
	}
}

//>>>>>>>>>>>>>>>>>>>>3.二叉排序树的查找算法<<<<<<<<<<<<<<<<<<<<<<<

/* （在二叉排序树中查找关键字） 
	函数：SearchBST
	参数：BiTree T 二叉排序树T 
	      KeyType key 关键字
	返回值：状态码，查找成功返回TRUE，否则返回FALSE 
	作用：在根指针T所指的二叉排序树中递归地查找其关键字等于key的数据元素
*/
Status searchBST(BiTree T, int key){
	//查找不成功 
	if(T == NULL) {
		//查找失败 
		return ERROR;
	}else if(key == T->data) {	
		//查找成功 
		return OK;
	}else if(key < T->data) {  	
		//递归地在左子树中继续查找
		return searchBST(T->lchild, key);
	}else {  
		//递归地在右子树中继续查找
		return searchBST(T->rchild, key);
	}   
}

/*  
	函数：InsertBST
	参数：BiTree *T 二叉排序树引用 
	      int key 在T中插入元素key
	返回值：状态码，插入成功返回TRUE，否则返回FALSE 
	作用：当二叉排序树T中不存在关键字等于key的数据元素时，
		  插入key并返回TRUE。否则返回FALSE
*/
Status insertBST(BiTree *T, int key){    //工作指针 
	BiTree s, p;
	//若查找不成功则将key插入到二叉排序树中 
	if(!searchBST(*T, key)){
		
		//申请一个新的结点，用于存放关键字e，并使s指向它 
		s = (BiTree)malloc(sizeof(BiNode));
		
		//检查内存申请是否成功 
		if(!s) { //if(!s) <=> if(s == NULL) 
	    	exit(OVERFLOW);
		}
		
		//将关键字e保存到s指向的新结点 
		s->data = key;
		
		//在二叉排序树中插入的结点一定是叶子结点
		//叶子结点左右孩子指针域均为NULL 
		s->lchild = s->rchild = NULL;
		
		//被插结点*s为新的根结点
		if(!p) { //if(!p) <=> if(p == NULL)
	    	
	    	//根指针T指向s指向的新结点 
			*T = s;
	    }else if(key < p->data) { //被插结点*s为左孩子 
			
			//将s指向的结点挂到p指向的被插结点的左孩子指针域上 
	    	p->lchild = s;
	    }else { //被插结点*s为右孩子			
			//将s指向的结点挂到p指向的被插结点的右孩子指针域上 
	    	p->rchild = s;
		}
		
		//插入成功 
		return TRUE; 
    }else {
		
		//树中已有关键字相同的结点，不再插入
		//插入失败 
    	return FALSE;      
	}
}


/*  
	函数：Delete
	参数：BiTree &p 指向二叉排序树中待删除的结点 
	返回值：状态码，删除成功返回TRUE，否则返回FALSE 
	作用：从二叉排序树中删除结点p，并重接他的左子树和右子树
*/
Status Delete(BiTree *p){
	
	//工作指针q指向被删除结点 
	BiTree q, s;
	
	//若p右子树为空则只需重接他的左子树
	//在左分支上删除一个没有右孩子的结点，只需要把它下面 
	//的左子树整体挂到它的双亲结点上就可以。
	//这里有一个技巧，p是一个引用，被修改后结果会被带回，
	//所以p指向的结点不论是其双亲的左孩子还是右孩子都是一样的操作
	//不会破坏二叉排序树左小右大的定义，
	//所以无需考虑p是其双亲的孩子。 左孩子还是右
	//if(!p->rchild) <=> if(p->rchild == NULL) 
	if(!(*p)->rchild){ 
		
		//q指向被删除结点 
		q = *p;
		
		//p指向被删结点的左子树根结点 
		p = &(*p)->lchild;
		
		//释放被删除结点的存储空间 
		free(q);
	}else if(!(*p)->lchild) {
	//左子树为空则只需重接他的右子树
	//在右分支上删除一个没有左孩子的结点，只需要把它下面 
	//的右子树整体挂到它的双亲结点上就可以。
	//if(!p->lchild) <=> if(p->lchild == NULL)
		
		//q指向被删除结点 
		q = *p;
		
		//p指向被删结点的右子树根结点
		p = &(*p)->rchild;
		
		//释放被删除结点的存储空间 
		free(q);
	}else{ 
	//左右子树均不空（最麻烦的情况）

		/**
		 * 需要删除节点(p)的左节点的最右节点(s)，是一个一定大于p的所有左节点，和小于p的所有右节点的数，p、s交换数据，删除s即可。
		 * s保证没有右节点，但是可能有左节点。s是谁？
		 * 		可能是p->lchild也就是p的左节点，这个时候，左节点的左节点接在p的左节点就可以
		 * 		可能是p左节点的最右节点，这个时候，s的左节点需要接在父节点的右节点
		*/
		//q指向被删除结点 
		q = *p;
		
		//s指向p的左子树根结点 
		s = (*p)->lchild;
		
		//转左，然后向右到尽头 
		//循环结束后，s指向p左子树的最右子树根结点 ，
		//也就是被删结点的前驱 
		//q指向s的前驱 
		while(s->rchild) {
			
			q = s;
			s = s->rchild;
		}
		
		//这里没有去把s指向的结点与p指向的结点进行调换
		//而是只替换里面的值。 s指向的结点就这样变成了被删除结点 
		//q此时也不再指向被删除结点。 
		(*p)->data = s->data;
		
		//p的左子树根结点有右孩子 
		if(q != *p) { //重接*q的右子树 
			
			//这种情况下s指向的结点将会被删除，
			//s指向的结点是q指向结点的右孩子，
			//且s指向的结点没有右子树，但不清楚是否有左子树 
			//删除后q的右孩子指针域就会腾出来 
			//所以要把s的左子树（左子树上所有结点值均>q结点值但<s结点值）
			//接到q的右子树上 
			q->rchild = s->lchild;
		}
		//p的左子树根结点没有右孩子
		else { //重接*q的左子树
		 
			//这种情况下s指向的结点将会被删除，
			//s指向的结点是q指向结点的左孩子，
			//且s指向的结点没有右子树，但不清楚是否有左子树 
			//s和p指向结点值互换之后，需要把S的左子树
			//接到p的左子树上，也就是q的左子树上 
			q->lchild = s->lchild; 
		}
		
		//释放s指向的结点 
		free(s);
	}
	
	//删除成功 
	return TRUE; 
}

/*  
	函数：DeleteBST
	参数：BiTree &T 二叉排序树引用 
	      KeyType key 待删除关键字 
	返回值：状态码，删除成功返回TRUE，否则返回FALSE 
	作用：若二叉排序树T中存在关键字等于key的数据元素时，
	      则删除该数据元素的结点并返回TRUE，否则返回FALSE
*/
Status deleteBST(BiTree *T, int key){
	
	//根结点为空，没必要扫描左右子树了，直接返回 
	if(!*T) {
		
		//不存在关键字等于key的数据元素
		return ERROR;
	}else{
		
		//找到关键字等于key的数据元素
		if(key == (*T)->data){
		    
			printf("找到关键字为%d的记录了，接下来要删除它！\n", key);
		    //if(Delete(T)) <=> if(Delete(T) == FALSE)
			if(Delete(T)){
		    	printf("删除成功！O(∩_ ∩)O\n");
		    	return OK; 
			}
			else{
				printf("删除失败！╮(╯▽╰)╭\n");
				return ERROR;
			}
		} 
		//待删除关键字小于当前结点关键字 
		else if(key < (*T)->data) {
			
			//递归地在左子树上删除关键字 
			return deleteBST(&(*T)->lchild, key);
		}
		//待删除关键字大于当前结点关键字 
		else {
			
			//递归地在右子树上删除关键字
			return deleteBST(&(*T)->rchild, key);
		} 
	}
} 


// --------------------------------- 树形打印--------------------------------------------------
// type:0表示根节点，1表示左子树，2表示右子树；level表示层级控制显示距离(层数)
void printTree(BiTree t,int type,int level){
	if(t == NULL){
		return;
	}
	printTree(t->rchild,2,level+1);
	switch(type){
		case 0:
			printf("%d\n", t->data);
			break;
		case 1:
			for(int a=0;a<level;a++){
				printf("\t");
			}
			printf("\\\n");
			for(int a=0;a<level;a++){
				printf("\t");
			}			
			printf(" %d\n", t->data);
			break;
		case 2:
			for(int a=0;a<level;a++){
				printf("\t");
			}
			printf(" %d\n", t->data);
			for(int a=0;a<level;a++){
				printf("\t");
			}
			printf("/\n");			
			break;		
	}
	printTree(t->lchild,1,level+1);
}

//-------------------------------------------主函数--------------------------------------------------- 
int main(){
    system("chcp 65001 > nul");

    BiTree T = NULL;
    int key;
    Status flag;
    int e;
	char menu_main[] = "\n--------------------------------二叉排序树引用版--------------------------------\n"
	                   "\t\t\t1.构建一棵二叉排序树。\n" 
	                   "\t\t\t2.在二叉排序树中查找关键字\n"
                       "\t\t\t3.在二叉排序树中插入关键字\n" 
					   "\t\t\t4.在二叉排序树中删除关键字\n"
                       "\t\t\t5.中序遍历二叉排序树\n"  
					   "\t\t\t6.退出程序\n\n"
	                   "请选择您所要执行的操作："; 
	while(1){
      	printf(menu_main);
		//逗号表达式以最后一个表达式值为准 
		char ch = getchar();
		switch(ch){  //接受一个字符到键盘  
            case '1':{
                createBST(&T);
				printTree(T,0,0);
				printf("您创建的二叉排序树的中序遍历序列如下：");
				inOrderTraverse(&T, printElement); 
				break;
            }
			case '2':{
				if(!T){
					printf("二叉排序树还未建立，请先建立后再操作！\n");
					break;
				}
				printf("请输入您想要查找的关键字(整数)：");
				scanf("%d", &key); 
				flag = searchBST(T, key);
				if(!flag)
				    printf("查找失败！\n");
				else
				    printf("查找成功！\n"); 
				break;
			}
			case '3':{
				if(!T){
					printf("二叉排序树还未建立，请先建立后再操作！\n");
					break;
				}
				printf("请输入您想要插入的关键字(整数)：");
				scanf("%d", &key); 
				flag=insertBST(&T, key);
				if(!flag){
				    printf("插入失败！\n");
				}else{
				    printf("插入成功！\n"); 
				}
				printTree(T,0,0);
				printf("插入操作后二叉排序树的中序遍历序列如下：");
				inOrderTraverse(&T, printElement);
				break;
			}
			case '4':{
				if(!T){
					printf("二叉排序树还未建立，请先建立后再操作！\n");
					break;
				}
				printf("请输入您想要删除的关键字(整数)：");
			    scanf("%d", &key); 
				deleteBST(&T, key);
				printTree(T,0,0);
				printf("删除操作后二叉排序树的中序遍历序列如下：");
				inOrderTraverse(&T, printElement);
				break;
			}
			case '5':{
				printTree(T,0,0);
				printf("二叉排序树的中序遍历序列：");
				inOrderTraverse(&T, printElement); 
				break;
			}
			case '6':{
				exit(0);
				break;
			}
			default :{
				printf("输入非法，请输入数字1-6！\n");
			}
		}

		printf("\n");
		system("pause");
		system("cls");
		fflush(stdin); 		 
    }

    return 0;
}